package com.huawei.od;

import java.util.Stack;

/**
 * 1081. 不同字符的最小子序列
 */
public class TestThree {

    public static void main(String[] args) {
        System.out.println(smallestSubsequence("dasfdsfsadasdsadsacffwqa"));
    }

    public static String smallestSubsequence(String s) {
        int[] a = new int[26];
        int[] b = new int[26];
        for (int i = 0; i < s.length(); i++) {
            // 计算每个字符出现的次数
            b[s.charAt(i) - 'a']++;
        }
        Stack<Character> stack = new Stack<>();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            b[s.charAt(i) - 'a']--;
            if (a[s.charAt(i) - 'a'] > 0) {
                continue;
            }
            while (!stack.isEmpty() && b[stack.peek() - 'a'] > 0 && s.charAt(i) < stack.peek()) {
                a[stack.pop() - 'a']--;
            }
            stack.push(s.charAt(i));
            a[s.charAt(i) - 'a']++;
        }
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.reverse().toString();
    }
}
